\bigskip
\bigskip
{\magonebf 5.5 Parameterized undirected graphs (UGRAPH)}

A parameterized undirected graph $G$ is an undirected graph whose nodes and 
edges contain additional (user defined) informations. Every node contains an 
element of a data type $vtype$, called the node type of $G$ and every edge 
contains an element of a data type $etype$ called the edge type of $G$. 
We use $<\{v,w\},y>$ to denote the undirected edge $\{v,w\}$ with information 
$y$ and $<x>$ to denote a node with information $x$. 



\bigskip
{\bf 1. Declaration of a parameterized undirected graph type}



\decltwo UGRAPH vtype etype 

introduces a new data type with name \name\ consisting of all
undirected parameterized graphs with node type $vtype$ and edge type $etype$.


\medskip
{\bf 2. Creation of a parameterized undirected graph }

\create G {}

creates an instance G of type \name and and initializes it to the empty graph.


\medskip
{\bf 3. \operations}

In addition to the operations of the data type $ugraph$ (see section 5.3):
\medskip
\+\op vtype/etype  inf {node/edge\ a}         
                          {returns the information of node/edge $a$ } 
\smallskip
\+\op void   assign {node/edge\ a,\ vtype/etype\ x} {}
\+\nop                    {makes $x$ the information of node/edge $a$ }
\smallskip
\+\op node   new\_node {vtype\ x}   
                          {adds a new node $<x>$ to $G$ and returns it}
\smallskip
\+\op edge new\_edge {node\ v,\ node\ w,\ etype\ x} {}
\+\nop                    {inserts the undirected edge $<\{v,w\},x>$ into }
\+\nop                    {$G$ by appending it to the adjacency lists of }
\+\nop                    {both $v$ and $w$ and returns it }
\smallskip
\+\op edge new\_edge {node\ v,\ node\ w,\ edge\ e1,\ edge\ e2,\ etype\ x,\ rel\_pos\ dir1=} {}
\+\nop                     {$after,\ rel\_pos\ dir2=after$)}
\+\nop                     {inserts the undirected edge $<\{v,w\},x>$ after}
\+\nop                     {(if $dir1=after$) or before (if $dir1=before$) }
\+\nop                     {the edge $e1$ into the adjacency list of $v$ and }
\+\nop                     {after (if $dir2=after$) or before (if $dir2=$}
\+\nop                     {$before$) the edge $e2$ into the adjacency list}
\+\nop                     {of $w$ and returns it.}

\bigskip
{\bf 4. Implementation}

Parameterized undirected graphs are derived from undirected graphs. All 
additional operations for manipulating the node and edge informations take 
constant time.

